Synchronization is a function that provides or maintains consistent copies of data between applications, computers, and devices. For example, a desktop computer may have desktop data sets regarding personal information management (“PIM”). A user of that desktop computer may desire to use that PIM data when she is away from her desktop computer. Therefore, she may desire access to the PIM data while using a laptop computer or a personal digital assistant (“PDA”) such as a phone or other device like a miniature device. In order to accommodate that desire, her laptop computer and PDA may each carry PIM data sets that correspond to the PIM data sets on the desktop computer. The role of the synchronization function is to give the user a common view of her data on each device. This role is generally accomplished by synchronization events when two or more of the devices synchronize.
A common technique for synchronizing devices is by using snapshots of data at a point in time and comparing current data to the snapshot to determine what has changed. For illustration purposes, FIG. 1 shows models for a desktop computer 100, a portable computer 110, and a PDA 120 for use in synchronization. Desktop computer 100 has PIM database 101, which keeps current information for PIM data sets that are edited or added on the desktop computer 100. Desktop computer 100 also has desktop snapshot database, which is a snapshot of the PIM data sets taken at some point in time but typically the time of a prior (perhaps, the most recent) synchronization. Similarly, portable computer 110 and PDA 120 have portable databases 111 and 121, respectively, for current PIM data.
Typical synchronization occurs by comparing each of desktop database 101, portable database 111, and PDA database 121 with snapshot database 102. Items in respective databases are identified as corresponding if those items share common identity data, which is typically a name in a PIM database, but may be any data property. During the compare operation, corresponding items are compared and the synchronization system assembles a list of data items that are new or changed in the active databases 101, 111, and 121 as compared to database 102. Finally, to finish out the synchronization, the list of new and changed data may be used to update all four databases 101, 102, 111, and 121.
In the described prior art synchronization process between three or more systems, the change of identity data on a record of one of the databases can be problematic. For example, assume a PIM database where the name property is used for identity data. Further, and referring to FIG. 1, assume that a record for Jon Doe (that is, a record including the value “John Doe” in a name property) has been synchronized from the portable 110 to the other systems. The two remaining systems synchronize at a later time, but sometime prior to synchronization the record value is changed on desktop database 101 from “Jon Doe” to “Jonathan Doe.” Since the name property is being used as identity data, if the PDA 120 synchronizes with desktop 100, the respective systems will not realize that the record for Jonathan Doe of desktop 100 actually corresponds with the record for Jon Doe of PDA 120. Thus, during synchronization with PDA 120, desktop 100 will believe that the record for Jon Doe from PDA 120 is a new record and will make a copy of the new record in database 101. In addition, PDA 120 will believe that the Jonathon Doe record is a new record and will make a copy of the new record in database 121. The unfortunate result is that both desktop 100 and PDA 120 have two records corresponding to the same person (reflected by only one record in portable 110). The problem is propagated if and when either desktop 100 or PDA 120 synchronizes with portable 110, which upon such synchronization will also obtain the substantively duplicative record and thus maintain two records for Jon(athon) Doe. These newly added records are also not recognized by the remaining peer, causing the records to be continually duplicated between the peers. While we have used a name as an example, the same problem occurs when synchronizing any type of data, e.g., other PIM data such as calendars, or even music or photo records.
Another problem that occurs when three or more synchronizing systems synchronize is known as the deletion problem. Referring again to FIG. 1, assume there is a record for Jane Doe that is exclusively held in desktop 100. When desktop 100 is synchronized with portable 110, then portable 110 will get the Jane Doe record. Similarly, when desktop 100 is synchronized with PDA 120, then PDA 120 will get the Jane Doe record. Further assume now that the user of PDA 120 notices the Jane Doe record and intentionally deletes that record. The problem occurs because, in synchronization of the prior art, a peer cannot identify a previously deleted record. Thus, the PDA 120, upon seeing the corresponding (undeleted) copy of the deleted record on one of the peers, believes the record to be a new record. When PDA 120 and portable 110 synchronize, therefore, that synchronization brings the unwanted Jane Doe record back to PDA 120, ultimately possibly frustrating the user who has deleted it intentionally already. This situation also results in a continual add/delete cycle between the peers, increasing the load on the system.
Yet another similar problem further illustrates issues in the prior art. For example, assume the devices of FIG. 1 are peers in a peer-to-peer system, and each of PDA 120 and portable 110 have synchronized with desktop 100, but PDA 120 and portable 110 have never synchronized with each other. Having each synchronized with desktop 100, PDA 120 and portable 110 are likely to carry a great number of corresponding records. However, their databases may also be significantly incongruous based upon, for example, any of the following circumstances: (i) any changes made to desktop 100 at a time between the synchronizations of PDA 120 and portable 110 will only be represented on the device that synchronized most recently; (ii) any records added or deleted on PDA 120 after its synchronization with desktop 100 will have little create inconsistencies with portable 110; (iii) any records added or deleted on portable 110 after its synchronization with desktop 100 will have little create inconsistencies with PDA 120; and (iii) any modifications (especially to an identity key property) on either PDA 120 or portable 110 will result in obvious inconsistencies as noted above. Yet, as exemplified above, not all these inconsistencies can be remedied through subsequent synchronization because PDA 120 and portable 110 cannot always identify truly corresponding records.
Background art and other techniques related to synchronization may be found in the following U.S. patents and copending patent applications, all of which are incorporated herein by reference: U.S. Pat. No. 5,710,922 “Method for synchronizing and archiving information between computer systems”; “A Method of Synchronising Between Three or More Devices” by Toby Paterson and Jerome Lebel, Ser. No. 10/853,306 filed May 24, 2004, now patent publication no. 2006/0031857; “A Method of Synchronising” by Toby Paterson and Jerome Lebel, Ser. No. 10/852,026 filed May 24, 2004, now patent publication no. 2004/0214926; “State Based Synchronization,” by Bertrand Serlet, Ser. No. 10/883,541, filed Jul. 1, 2004, now patent publication no. 2006/0069809; and “Apparatus and Method For Peer-To-Peer N-Way Synchronization In A Decentralized Environment,” by Joe Holt, Ser. No. 11/157,647, filed Jun. 21, 2005. In view of the discussion herein as well as the other problems existing in the prior art, certain embodiments of the invention propose a synchronization system that provides for the identification of truly corresponding records and thus resolves the problems discussed above.